Internet Info 1994 March

home *** CD-ROM | disk | FTP | other *** search

/ Internet Info 1994 March / Internet Info CD-ROM (Walnut Creek) (March 1994).iso / inet / internet-drafts / draft-estrin-sdrp-01.txt < prev next >

Wrap

Text File | 1993-03-03 | 42.0 KB | 988 lines

Network Working Group Deborah Estrin INTERNET DRAFT USC Tony Li cisco Systems Yakov Rekhter T.J. Watson Research Center, IBM Corp. 10/10/92 Revision 0.93 Expiration Date: 04/10/92 Source Demand Routing Protocol Specification (Version 1). Status of this Memo This document defines an inter-autonomous system routing protocol for the Internet. This document specifies an IAB standards track protocol for the Internet community, and requests discussion and suggestions for improvements. Please refer to the current edition of the "IAB Official Protocol Standards" for the standardization state and status of this protocol. Distribution of this document is unlimited. This document is an Internet Draft. Internet Drafts are working documents of the Internet Engineering Task Force (IETF), its Areas, and its Working Groups. Note that other groups may also distribute working documents as Internet Drafts. Internet Drafts are draft documents valid for a maximum of six months. Internet Drafts may be updated, replaced, or obsoleted by other documents at any time. It is not appropriate to use Internet Drafts as reference material or to cite them other than as a "working draft" or "work in progress". 1 Overview The purpose of SDRP is to support source-initiated selection of inter-domain routes to complement the intermediate-node route selection provided by BGP ([1], [2], [3]) or IDRP ([4]). This document refers to such source-initiated routes as "SDRP routes". The protocol makes minimal assumptions about the distribution and acquisition of routing information needed to construct the SDRP routes. These minimal assumptions are believed to be sufficient for the existing Internet. Future versions of the protocol will extend capabilities in this area and others in a largely backward-compatible manner. This version of the protocol sends all packets with the complete SDRP route in the SDRP header. Future versions will address route setup and other enhancements and optimizations. 2 Model of operations An Internet can be viewed as a collection of routing domains interconnected by means of common Layer 2 (Data Link Layer) subnetworks, and Border Routers (BRs) attached to these subnetworks. A BR belongs to only one domain. A pair of BRs, each belonging to a different domain, but attached to a common subnetwork, form an inter-domain connection. By definition, packets that traverse multiple domains must traverse BRs of these domains. Note that a single physical router may act as multiple BRs for the purposes of this model. A pair of domains is said to be adjacent if there is at least one pair of BRs, one in each domain, that form an inter-domain connection. Each domain has a globally unique identifier, called a Domain Identifier (DI). All the BRs within a domain need to know the DI assigned to the domain. Management of the DI space is outside the scope of this document. This document assumes that Autonomous System (AS) numbers are used as DIs. Further, a domain path (or simply path) in this document refers to a list of DIs as taken from a BGP AS path or an IDRP RD path. We refer to a route as the combination of a network address and a domain path. The network addresses are represented by NLRI (Network Layer Reachability Information) as described in [3]. This document assumes that routing domains are congruent to the autonomous systems. Thus, within the content of this document terms autonomous system and routing domain can be used interchangeably. An SDRP route is defined as a sequence of domains, syntactically expressed as a sequence of DIs (autonomous system numbers). Each SDRP route has a flag associated with it indicating whether it is strict or loose. A strict SDRP route means that any pair of consecutive DI entries in the SDRP route must represent a pair of adjacent domains. A loose SDRP route may also allow a pair of consecutive DI entries in the SDRP route to be separated by other domains that are not listed in the route. It is assumed that a BR participates in the intra-domain routing protocol(s) (IGPs) of the domain to which the BR belongs. Thus, a BR may forward a packet to any other BR in its own domain using intra- domain routing procedures. Forwarding a packet between two BRs that form an inter-domain connection requires neither the intra-domain nor the inter-domain routing procedures (an inter-domain connection is a common Layer 2 subnetwork). While SDRP does not require that all domains have a common network layer protocol, all the BRs across the domains spanning a given SDRP route are required to support a common network layer. This document specifies SDRP operations when that common network layer protocol is IP ([5]). While this document requires all the BRs to support IP, the document does not preclude a BR from additionally supporting other network layer protocols as well (e.g., CLNP, IPX, AppleTalk). If a BR supports multiple network layers, then for the purposes of this model, the BR must maintain multiple Forwarding Information Bases (FIBs), one per network layer. Forwarding an IP packet along an SDRP route is accomplished by encapsulating the packet in an SDRP packet. An SDRP packet consists of the SDRP header followed by the SDRP data. The SDRP header carries the SDRP route constructed by the domain that originated the SDRP packet. The SDRP data carries the original packet that the source domain decided to forward via SDRP. An SDRP packet is carried across domains as the data portion of an IP packet with protocol number 42. This document refers to the IP header of a packet that carries an SDRP packet as the delivery IP header (or just the delivery header). This document refers to the packet carried as SDRP data as the payload packet, and the network layer header of the payload packet is the payload header. Thus, an SDRP Packet can be represented as follows: +-------------------+--------------+------------------- | Delivery header | SDRP header | SDRP data | (IP header) | | (Payload packet) +-------------------+--------------+-------------------- Each SDRP route may have an MTU associated with it. An MTU of an SDRP route is defined as the maximum length of the payload packet that can be carried without fragmentation of an SDRP packet. Procedures for MTU discovery are specified in Section 9. It is assumed that a BR participates in either BGP or IDRP. A BR participating in SDRP augments its FIBs with a D-FIB that contains routes to domains. A route to a domain is a tuple that consists of a destination domain (expressed as a DI), and the network layer address of the next-hop BR. D-FIBs are constructed based on the information obtained from either BGP, IDRP, or configuration information. An SDRP packet is forwarded across multiple domains by utilizing the forwarding databases (both FIBs and D-FIBs) maintained by the BRs. The operational status of SDRP routes is monitored via passive (Error Reporting) and active (Route Probing) mechanisms. The Error Reporting mechanism provides the originator of the SDRP route with a failure notification. The Probing mechanism provides the originator of the SDRP route with confirmation of a route's feasibility. 3 SDRP Packet format The total length of an SDRP packet (header plus data) can be determined >from the information carried in the delivery IP header. The length of the payload packet can be determined from the total length of an SDRP packet and the length of its SDRP Header. The following describes the format of an SDRP packet. For a data packet: 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Ver |S|P|D| | BR Hop Count |SourceProtoType| Payload Type | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Source Route Identifier | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Prefix | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | PrefixLength |SrcRouteLength | NextDomainPtr | Source Route ... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Payload .... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ For a control packet: 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Ver |S|P|D| | Notification |SourceProtoType| Payload Type | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Source Route Identifier | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Target Border Router | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Prefix | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | PrefixLength |SrcRouteLength | NextDomainPtr | Source Route ... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Payload .... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Version and Flags (1 octet) The SDRP version number and control flags are coded in the first octet. Bit 0 is the most significant bit, bit 7 is the least significant bit. Version (bits 0 though 2) The first three bits contain the Version field indicating the version number of the protocol. The value of this field is set to 1. Flags (bits 3 through 7) Loose/Strict Source Route (bit 3) The Loose/Strict Source Route indicator is used when making a forwarding decision (see Section 5.2). If this bit is set to 1, it indicates a Strict Source Route. If this bit is set to 0, it indicates a Loose Source Route. Probe Indicator (bit 4) The Probe Indicator is used by the originator of the route to request verification of the route's feasibility (see Sections 4 and 7.1). If this bit is set to 1, it indicates that the originator is probing the route. Data packet/Control packet (bit 5) If the bit is set to 1, then the packet carries data. Otherwise, the packet carries control information. The rest of the Flags field is transmitted as zero, and should be ignored on receipt. BR Hop Count (1 octet) This field is present only in data packets. The BR Hop Count field carries the maximum number of BRs an SDRP data packet may traverse. It is decremented by 1 as an SDRP data packet traverses a BR. Once the BR Hop Count field reaches the value of 0, the BR should discard the data packet and generate a control packet (see Section 5.2.4). Notification Code (1 octet) This field is present only in control packets. This document defines the following values for the Notification Code: 1 - No Route Available 2 - Strict Source Route Failed 3 - Transit Policy Violation 4 - BR Hop Count Exceeded 5 - Probe Completed 6 - Unimplemented SDRP version Source Route Protocol Type (1 octet) The Source Route Protocol Type fields indicates the type of Domain Identifiers (DIs) that appear in the source route. The value 1 in this field indicates that the DIs are Internet Autonomous System numbers. Payload Protocol Type (1 octet) The Payload Protocol Type field indicates the protocol type of the payload. If the payload is an IP datagram, then this field should contain the value 1. Source Route Identifier (4 octets) The BR that originates the SDRP packet should insert a 32 bit value in this field which will serve as an identifier for the source route. This value needs to be unique only in the context of the originating BR. Target Border Router (4 octets) This field is present only in control packets. The Target Border Router contains one of the IP addresses of the BR originating the SDRP packet that triggered the control packet to be returned. Reserved (3 octets) This field is reserved for future use. Prefix (4 octets) The Prefix field contains an IP address prefix. Only the number of bits specified in the Prefix Length are significant. The Prefix field is used to prevent routing loops when using BGP or IDRP to route to the next AS in a loose source route (see Section 4). Prefix Length (1 octet) The Prefix Length field indicates the length in bits of the IP address prefix. A length of zero indicates a prefix that matches all IP addresses. Source Route Length (1 octet) The Source Route Length field indicates the length in octets of the domain level source route carried in the SDRP Header. Next Domain Pointer (1 octet) The Next Domain Pointer field indicates the offset of the high-order byte of the next domain identifier along the route that the packet has to be forwarded. This offset is relative to the start of the Source Route field; so if the value of the Next Domain Pointer field equals the value of the Source Route Length field, then the entire source route has been completed. All other source routes are said to be incomplete. Source Route (variable) Contains a sequence of domain identifiers (expressed as Autonomous System numbers) that determines the sequence of domains to be traversed. Each autonomous system is encoded as 2 octets. Payload (variable) The Payload field carries the datagram originated by the end- system within the domain that constructed the SDRP packet. The Payload field forms the data portion of the SDRP packet. In a control packet this field may be empty or may carry the payload header of the packet that triggered the control message (see 5.2.5). Note that there is no padding between the Source Route and the Payload, and that the Payload may start at any arbitrary octet boundary. 4 Originating SDRP Data packets This document assumes that a BR that originates SDRP packets is preconfigured with a set of SDRP routes. Procedures for constructing these routes are outside the scope of this document. It is assumed that a BR has sufficient information to ascertain whether an IP datagram received by the BR was originated by a host within the domain the BR belongs to. Procedures for acquiring this information are outside of the scope of this document. When a BR receives an IP datagram originated by a host within its domain, the BR uses the information in the datagram and the local criteria to determine whether the datagram should be forwarded along a particular SDRP route. Associated with each set of criteria is a set of one or more SDRP routes which should be used to route matching packets. The exact nature of the criteria is a local matter. The only restriction this document places on the applicability of SDRP routes is that an IP datagram that contains a strict source route should not be forwarded along an SDRP route. If the BR decides to forward the datagram along a particular SDRP route, the BR constructs the SDRP packet by placing the original datagram into the Payload field of the SDRP packet and constructing the SDRP header based on the selected SDRP route. The Next Hop pointer is set to 0 (the first entry in the Source Route field of the SDRP packet). The value of the Time To Live field in the payload header should be copied into the BR Hop Count field of the SDRP header. The source address field in the delivery header should contain an IP address of the BR. The value of the Don't Fragment flag of the delivery header is copied from the Don't Fragment flag of the payload header. The value of the Type Of Service field in the delivery header is copied from the Type Of Service field in the payload header. If the payload header contains an IP security option, that option is replicated as an option in the delivery header. All other IP options in the payload header must be ignored. If the selected SDRP route is a loose source route, then the BR consults the BGP or IDRP path table to find a path to the next hop AS. The BR chooses one such path, then selects one of the NLRI associated with this path. This prefix and its length are placed in the Prefix and Prefix Length fields of the SDRP header. If IDRP is used, then the TOS corresponding to this route is copied into the TOS field in the delivery header. Subsequent BRs will use this prefix to look up the next BGP or IDRP hop, thereby preventing hop-by-hop routing loops along the loose source route. In essence, when a BR along a loose source route selects an NLRI prefix, it is selecting a single route to the next hop AS, and forcing subsequent BR's along the path to choose the same path. Once the BGP or IDRP delivers the packet to this next-hop AS, SDRP continues forwarding it along the rest of the source route. The resulting SDRP packet is then forwarded as described in Section 5.2.2. If a BR decides to forward a datagram along a particular SDRP route, and the payload header has Don't Fragment flag set to 1, and the length of the datagram is greater than the MTU associated with the SDRP route (if the MTU is defined), the BR should generate the ICMP Destination Unreachable message with a code meaning "fragmentation needed and DF set" in accordance with ([6]). The BR should discard the original datagram. If a BR has learned an MTU for a particular SDRP route, either via ICMP messages or via configuration information, and it determines that an SDRP packet must be fragmented before transmission, then it must first fragment the payload packet using normal IP fragmentation. SDRP packets are then constructed for each fragment, as describe above. A BR may use the SDRP packets originated by the BR to verify the feasibility of its SDRP routes. To do this the BR sets the value of the Probe Indicator field in the SDRP packet to 1. Receipt of an SDRP control packet by the originating BR with the "Probe Completed" Notification Code (see Section 7.1) indicates feasibility of the SDRP route. Persistent lack of SDRP control packets with the "Probe Completed" Notification Code should be used as an indication that the associated SDRP route is unfeasible. 5 Processing SDRP packets We say that a BR receives an SDRP packet if the destination address field in the delivery header of the packet arriving at the BR contains one of the IP addresses of the BR. When a BR receives an SDRP packet, the BR extracts the Source Route Protocol field from the SDRP header. Processing of an SDRP packet with the value of the Source Route Protocol field other than 1 is outside the scope of this document. If the value of this field is 1, the BR should proceed as follows. 5.1 Supporting Transit Policies A BR may be able to verify that a packet that it is given to forward does not violate any of the transit policies, if any, of the domain to which the BR belongs. Specific verification mechanisms are a matter that is local to the BR and are outside the scope of this document. The only restriction on the verification mechanisms is that they may take into account only the contents of the SDRP header, the payload header, and transport protocol header of the payload packet. If the BR detects that the SDRP packet violates a domain's transit policy it sends back an SDRP control packet and discards the violating packet. SDRP control packets are not subject to transit policies. If a BR does not discard an SDRP packet due to a transit policy violation, then the BR attempts to forward it as specified in Section 5.2. With SDRP a domain may enforce its transit policies by applying filters based on the information present in the IP Header. For example a BR may initially filter out all SDRP traffic from all possible sources. A filter that allows certain SDRP traffic from selected sources to pass through the BR could then be installed dynamically as a result of a local check on a packet. Once a packet passes the check against local transit policies, the appropriate filter is installed into the forwarding database to allow subsequent packets to pass through. Thus, by caching appropriate filtering information, a transit domain can efficiently enforce transit policies. Other transit policy enforcement mechanisms and implementation techniques are not precluded by this document. 5.2 Forwarding SDRP packets Procedures for forwarding of an SDRP packet depend on whether the BR has the routing information needed to forward the packet; whether the SDRP route has been completely traversed or not; whether the SDRP route is strict or loose, and whether the packet is data or control. When forwarding an SDRP packet (either data or control) a BR should not modify the following fields in the delivery header: Source Address Don't Fragment flag 5.2.1 Forwarding algorithm pseudo-code The following pseudo-code gives an overview of the SDRP forwarding algorithm. Please consult the text below for more details. Let LOCAL_DI be the DI of the domain of the local system, NEXT_DI be the next DI in the source route (or undefined if the source route has been completed), and let NEXT_HOP be the IP address of the next hop BR (as found in the D-FIB) if the packet is forwarded using SDRP. We say that NEXT_DI is adjacent if the local domain is adjacent to the domain that has NEXT_DI as its DI. Normal IP forwarding refers to forwarding that can be accomplished using FIBs constructed via BGP, IDRP or one or more IGPs. if the packet is a control packet begin if the Target Border Router equals an address assigned to the local BR begin remove the delivery header process information carried in the control packet return else if the packet can be forwarded using normal IP forwarding begin set Next Domain Pointer to Source Route Length forward the packet using normal IP forwarding return end if end if end if if the version field is not 1 begin if the packet is a data packet begin generate a control packet with "Unimplemented SDRP version" end if discard the packet return end if if the packet is a data packet begin decrement the BR Hop Count field if the BR Hop Count field is 0 begin generate a control packet with "BR Hop Count Exceeded" discard the data packet return end if if the packet violates transit policy begin generate a control packet with "Transit Policy Violation" discard the data packet return end if end if if the source route has not been completed begin while the NEXT_DI is equal to the LOCAL_DI begin update the value of the Next Domain Pointer field set NEXT_DI to the next DI in the source route if the source route is loose and NEXT_DI is not equal to the LOCAL_DI begin select a BGP or IDRP route with a path that includes NEXT_DI copy the NLRI from the route to the Prefix Length and Prefix if it was an IDRP route, set appropriate TOS in delivery header end if end while end if if the source route has not been completed begin if there is no route to NEXT_DI begin if the packet is a data packet begin generate a control packet with "No Route Available" end if discard the packet return end if if the source route is strict and NEXT_DI is not adjacent begin generate a control packet with "Strict Source Route Failed" discard the packet return end if if the source route is loose begin select the routing infomation matching the Prefix field if the routing information was an aggregate formed locally begin select a BGP or IDRP route with a path that includes NEXT_DI copy the NLRI from the route to the Prefix Length and Prefix if it was an IDRP route, set appropriate TOS in delivery header end if end if set NEXT_HOP from the routing information for NEXT_DI route packet to NEXT_HOP using normal IP forwarding else if the packet is a data packet begin remove the delivery header and the SDRP Header if there is no normal IP route to the payload destination begin generate a control packet with "No Route Available" discard the packet return end if forward the payload using normal IP forwarding if the probe bit is set begin generate a control packet with "Probe Completed" end if else discard the control packet end if end if 5.2.2 Handling an SDRP control packet. An SDRP control packet is indicated by 0 in the Data packet/Control packet bit in the Flags field in the SDRP Header. If the Target Border Router field of the received SDRP packet contains an IP address that is assigned to an interface attached to the local system, then the local system should use the information carried in the Notification Code field, the Source Route Identifier field and the information carried in the Payload field to update the status of its SDRP routes. Details of such procedures are described in Section 7. Otherwise, the local systems checks whether it can forward the packet to the BR specified in the Target Border Router field by using the routing information present in its local FIB. If forwarding is possible then the local system sets the destination address of the delivery header to the address specified in the Target Border Router field, and hands the packet off for normal IP forwarding. If normal IP forwarding is impossible then the packet may be forwarded in the same manner as an SDRP data packet (described below) but with the following exceptions. Control packets do not carry a BR Hop Count, which is neither referenced nor decremented when forwarding. Control packets are not subject to transit policies. If the version field of a control packet is not understood, no control packet should be generated. If the source route is complete and the packet still cannot be forwarded via normal IP routing, the packet should be dropped. 5.2.3 Handling an SDRP data packet. An SDRP data packet is indicated by a one in the Data packet/Control packet bit in the Flags field in the SDRP Header. An SDRP data packet is forwarded by sending the packet along the source route in the SDRP Header. When the source route is complete, the payload may be removed from the data packet and forwarded normally. Further details are described below. 5.2.3 Checking the SDRP version number An SDRP packet that has a version number other than 1 should be discarded. If the SDRP packet was a data packet, then a control packet with the Notification Code "Unimplemented SDRP version" should be generated as specified in section 6. 5.2.4 Decrementing and checking BR Hop Count If an SDRP data packet is to be forwarded, the BR Hop Count field should be decremented. If the resulting value is zero, then a control packet with the Notification Code "BR Hop Count Exceeded" should be generated as specified in section 6, and the packet should be discarded. The payload of the control packet should carry the payload header followed by 64 bits of the payload data of the data packet. 5.2.5 Enforcing transit policies A BR may examine any data packet to verify if it complies with local transit policies, as described in section 5.1. If the verification fails, the BR generates a control packet. If the verification referred to only the contents of the SDRP header, then the payload field of the control packet should be empty. If the verification referred to both the contents of the SDRP header and the payload header, then the payload field of the control packet should carry the payload header. If the verification referred to transport protocol header, then the payload field of the control packet should carry the payload header and the transport header. The Notification Code field of the SDRP header in the control packet is set to Transit Policy Violation. The procedures for constructing the rest of the SDRP Header of the control packet are specified in Section 6. 5.2.6 Incomplete source routes If a BR receives an SDRP packet with an incomplete source route, the BR extracts the DI of the next domain from the Source Route field. The BR locates the high-order byte of the appropriate DI by using the Next Domain Pointer field as an offset relative to the start of the Source Route field. If the extracted DI of the next domain is the same as the DI of the local domain, then the Next Domain Pointer should be incremented by two (the size of a DI). If the source route is still incomplete, then this procedure should be repeated until either the source route is complete, or the extracted DI is not the same as the DI of the local system. If upon the termination of the procedure the source route becomes complete, see section 5.2.9. If the Next Domain Pointer has been advanced as a result of this section, then the BR must consult its D-FIB and select a route with a path which includes the extracted DI. The NLRI for this route should be copied into the Prefix Length and Prefix fields. Otherwise, the local BR proceeds as follows. 5.2.6.1 Finding a route to the next domain Given the DI of the next domain, the BR next consults its D-FIB. If the source route is loose, then the BR should use the information carried in the Prefix and Prefix Length as an index into its BGP or IDRP routing table. If it finds a matching route then it must select the corresponding D-FIB entry. If the route was formed locally by aggregation, then the BR must consult its D-FIB and select any route with a path which includes the extracted DI. The NLRI for this route should be copied into the Prefix Length and Prefix fields. Otherwise, if no entry exists in the D-FIB for the next domain, then the packet should be discarded. If the packet was a data packet, a control message with Notification Code "No Route Available" should be generated as specified in Section 6. No other actions are necessary. If there is a D-FIB entry, the BR next examines the packet to determine if the packet specified a strict source route. If so, and the next domain is not adjacent to the local domain, then a control packet with the Notification Code "Strict Source Route Failed" should be generated as specified in section 6 and the original packet should be discarded. No other actions are necessary. The D-FIB entry includes the IP address of the next SDRP-speaking BR to which the SDRP packet should be routed. The destination address in the delivery header is replaced by this address. The resulting packet can then be forwarded using normal IP forwarding. 5.2.6.2 Last Hop Optimization A small optimization can be performed if there is only a single DI in the source route that has not been traversed. In this case, if there is a route in the FIB for the destination address of the payload packet, and the next DI in the source route indicates an adjacent domain, and the FIB route passes through this domain, then the source route may be considered complete and processing may proceed as in section 5.2.7. 5.2.7 Completed source routes If the SDRP packet received by a BR with a completed source route is a control packet and if the Target Border Router field carries an IP address assigned to the BR, then the packet should be processed as specified in Section 7. Otherwise, if the SDRP packet is a control packet, and the packet cannot be forwarded via either SDRP or normal IP forwarding and the packet should be dropped. If the packet is an SDRP data packet received by a BR, then the payload packet may be extracted from the SDRP packet. The BR Hop Count field should be copied from the SDRP header into the IP TTL field in the payload header. The resulting payload packet is then forwarded using normal IP forwarding. If there is no FIB entry for the destination, then the packet should be discarded and a control message with Notification Code "No Route Available" should be generated as specified in Section 6. If the packet can be forwarded and if the Probe Indication bit is set to one in the SDRP header, then a control message with Notification Code "Probe Completed" should be generated as specified in section 6. The payload of the control packet should carry the first 64 bits of the SDRP header and the payload header. 6 Originating SDRP control packets A BR sends a control packet in response to either error conditions, or to successful completion of a probe request (indicated via Probe Indication in the Flags field). The Data Packet/Control Packet field is set to indicate Control Packet. The following fields are copied from the SDRP header of the Data packet that caused the generation of the Control packet: Loose/Strict Source Route Source Route Protocol Type Source Route Identifier Source Route Length field Payload Protocol Type A Control packet should not carry a Probe Indication field. The Target Border Router is copied from the source IP address of the delivery header of the SDRP Data packet. The BR generating a control packet checks its FIB for a route to the destination depicted by the Target Border Router field. If such a route is present, then the value of the Destination Address field in the delivery header is set to the Target Border Router, the Source Address field in the delivery header is set to the IP address of one of the interfaces attached to the local system, and the packet is forwarded via normal IP forwarding. If the FIB does not have a route to the destination depicted by the Target Border Router field, the local system constructs the Source Route field of the Control packet by reversing the SDRP route carried in the Source Route field of the Data packet, sets the value of the Next Hop Pointer to the value of the Source Route Length field minus the value of the Next Hop Pointer field of the SDRP data packet that caused generation of the Control Packet. The contents of the Payload field depends on the reason for generating a control packet. The resulting packet is then handled via SDRP Forwarding procedures described in Section 5.2. 7. Processing control information A BR participating in SDRP may receive control information in two forms, SDRP control packets from other BRs and ICMP messages from routers that do not participate in SDRP, but are involved in forwarding SDRP packets. 7.1 Processing SDRP control packets If after processing an SDRP control packet a BR determines that the packet carries information about SDRP routes used by the BR, the BR may use the information in the SDRP control packet to select alternate routes if available and to mark the affected routes as unfeasible. To correlate information carried in the SDRP control packet with the SDRP routes used by the BR, the BR uses information carried in the SDRP header of the control packet and optionally in the SDRP payload of the control packet (if present). In general receipt of any SDRP control packet that carries one of the following Notification Codes No Route Available Strict Source Route Failed Unimplemented SDRP version indicates that the corresponding SDRP route is presently not feasible and thus should not be used for packet forwarding. The BR may at some later point attempt to use an SDRP route that was marked as infeasible. Receipt of an SDRP control packet that carries the "Transit Policy Violation" Notification Code shall be interpreted as follows: If the control packet carries no payload data then the corresponding SDRP route violates transit policy regardless of the content of the payload packet carried along that route. If the control packet carries only the payload header, then the corresponding SDRP route violates transit policy due to the content of the payload header. If the control packet carries the payload header and the transport header, then the corresponding SDRP route violates transit policy for a particular combination of the contents of the payload and transport headers. Receipt of an SDRP control packet that carries "Probe Completed" Notification Code indicates that the corresponding SDRP route is feasible. If a BR receives an SDRP control packet that carries "BR Hop Count Exceeded" Notification Code, the BR should use the information in the payload of the Control packet to construct an ICMP Time Exceeded Message with code "time to live exceeded in transit" and send the message to the host indicated by the source address in the Payload Header. 7.2 Processing ICMP messages To correlate information carried in the ICMP messages with the SDRP routes used by the BR, the BR uses the last 4 octets of the ICMP message. These bytes carry the Source Route Identifier of the SDRP route used by the BR. ICMP Destination Unreachable messages with a code meaning "fragmentation needed and DF set" should be used for SDRP MTU discovery as described in Section 9. All other ICMP Unreachable messages indicate that the associated route is infeasible. 8. Constructing D-FIBs. A BR constructs its D-FIB as a result of participating in either BGP or IDRP. A BR must advertise via BGP or IDRP a route to destinations within its domain to all of its external peers (BRs in adjacent domains). A BR may also advertise (via BGP or IDRP) to its external peers routes to destinations within other domains, but are installed in the BR's D-FIB. If a BR receives a route to an adjacent domain from a BR in that domain and selects that route as part of its BGP or IDRP Decision Process, then it must propagate this route (via BGP or IDRP) to all other BRs within its domain. A BR may also propagate such a route if it depicts an autonomous system other than the adjacent domain. 9. SDRP MTU Discovery To participate in Path MTU Discovery ([6]) a BR may maintain information about the maximum length of the payload packet that can be carried without fragmentation along a particular SDRP route. SDRP provides two complimentary techniques to support MTU Discovery. The first one is passive and is based on the receipt of the ICMP Destination Unreachable messages (as described in Section 7.2). By combining information provided in the ICMP message with local information about the SDRP route the local system can determine the length of a payload packet that would require fragmentation. The second one is active and employs the Probe Indicator bit. If an SDRP data packet that carries the Probe Indicator bit in the SDRP header and Don't Fragment flag in the delivery header triggers the last BR on the SDRP route to return an SDRP Control packet (with the Notification Code "Probe Completed"), then the information carried in the payload header of the control packet can be used to determine the length of the payload packet that went through the SDRP route without fragmentation. References [1] Lougheed, K., and Y. Rekhter, "A Border Gateway Protocol 3 (BGP- 3), RFC 1267, cisco Systems, T.J. Watson Research Center, IBM Corp., October 1991. [2] Rekhter, Y., and P. Gross, "Application of the Border Gateway Protocol in the Internet", RFC 1268, T.J. Watson Research Center, IBM Corp., ANS, October 1991. [3] Y. Rekhter and T. Li, "A Border Gateway Protocol 4 (BGP-4)", Internet Draft, cisco Systems, T.J. Watson Research Center, IBM Corp., September 1992. [4] S. Hares, "IDRP for IP", Internet Draft, NSFNET/MERIT, June 1992 [5] Postel, J., "Internet Protocol - DARPA Internet Program Protocol Specification", RFC 791, DARPA, September 1981. [6] J. Mogul, S., and S. Deering, "Path MTU Discovery", RFC1191, November 1990